﻿
Imports osi.root.connector

Partial Public Class bt(Of T)
    Partial Protected Friend Class node
        Private ReadOnly b As box
        Private ReadOnly hb As heighted_box
        Private ReadOnly wb As weighted_box
        Private l As node
        Private r As node
        Private p As node

        Public Sub New(ByVal b As box)
            Me.b = b
            Me.hb = TryCast(b, heighted_box)
            Me.wb = TryCast(b, weighted_box)
        End Sub

        Private Function left_linked(ByVal n As node) As Boolean
            Return (n Is Nothing AndAlso
                    Not has_left_child()) OrElse
                   (Not n Is Nothing AndAlso
                    has_left_child() AndAlso
                    object_compare(left_child(), n) = 0 AndAlso
                    k_assert(left_child().has_parent()) AndAlso
                    k_assert(object_compare(left_child().parent(), Me) = 0))
        End Function

        Private Function right_linked(ByVal n As node) As Boolean
            Return (n Is Nothing AndAlso
                    Not has_right_child()) OrElse
                   (Not n Is Nothing AndAlso
                    has_right_child() AndAlso
                    object_compare(right_child(), n) = 0 AndAlso
                    k_assert(right_child().has_parent()) AndAlso
                    k_assert(object_compare(right_child().parent(), Me) = 0))
        End Function

        Private Function parent_linked(ByVal n As node) As Boolean
            Return (n Is Nothing AndAlso
                    Not has_parent()) OrElse
                   (Not n Is Nothing AndAlso
                    has_parent() AndAlso
                    object_compare(parent(), n) = 0 AndAlso
                    k_assert((n.has_left_child() AndAlso
                              object_compare(n.left_child(), Me) = 0) OrElse
                             (n.has_right_child() AndAlso
                              object_compare(n.right_child(), Me) = 0)))
        End Function

        Public Sub append_to_min(ByVal n As node)
            k_assert(Not n Is Nothing)
            min().replace_left(n)
        End Sub

        Public Sub append_to_max(ByVal n As node)
            k_assert(Not n Is Nothing)
            max().replace_right(n)
        End Sub

        Public Sub replace_left(ByVal n As node)
            l = n
            If Not n Is Nothing Then
                n.p = Me
            End If
        End Sub

        Public Sub replace_right(ByVal n As node)
            r = n
            If Not n Is Nothing Then
                n.p = Me
            End If
        End Sub

        Public Sub clear_left()
            l = Nothing
        End Sub

        Public Sub clear_right()
            r = Nothing
        End Sub

        Public Sub clear_parent()
            p = Nothing
        End Sub

        'return the min node of the subtree rooted by this node
        Public Function min() As node
            Dim n As node = Nothing
            n = Me
            While n.has_left_child()
                n = n.left_child()
            End While
            k_assert(Not n Is Nothing)
            Return n
        End Function

        'return the max node of the subtree rooted by this node
        Public Function max() As node
            Dim n As node = Nothing
            n = Me
            While n.has_right_child()
                n = n.right_child()
            End While
            k_assert(Not n Is Nothing)
            Return n
        End Function

        Public Sub replace_parent_subtree(ByVal c As node)
            If has_parent() Then
                If is_left_subtree() Then
                    parent().replace_left(c)
                Else
                    k_assert(is_right_subtree())
                    parent().replace_right(c)
                End If
            ElseIf Not c Is Nothing Then
                c.clear_parent()
            End If
        End Sub

        Public Sub clear_parent_subtree()
            If has_parent() Then
                If is_left_subtree() Then
                    parent().clear_left()
                Else
                    k_assert(is_right_subtree())
                    parent().clear_right()
                End If
            End If
        End Sub

        Private Shared Function replace_by(ByVal a As node, ByVal b As node) As node
            k_assert(Not a Is Nothing)
            k_assert(Not b Is Nothing)
#If DEBUG Then
            If a.has_left_child() Then
                k_assert(a.left_child().max().compare(b) < 0)
            End If
            If a.has_right_child() Then
                k_assert(a.right_child().min().compare(b) > 0)
            End If
#End If
            b.replace_left(a.left_child())
            b.replace_right(a.right_child())
            a.replace_parent_subtree(b)

            b.debug_assert_structure()

            Return b
        End Function

        Private Shared Function replace_by_left_subtree(ByVal a As node) As node
            k_assert(Not a Is Nothing)
            k_assert(a.has_left_child())
            k_assert(Not a.has_right_child() OrElse Not a.left_child().has_right_child())
            Dim b As node = Nothing
            b = a.left_child()
            a.replace_parent_subtree(b)
            If a.has_right_child() Then
                b.replace_right(a.right_child())
            End If

            b.debug_assert_structure()

            Return b
        End Function

        Private Shared Function replace_by_right_subtree(ByVal a As node) As node
            k_assert(Not a Is Nothing)
            k_assert(a.has_right_child())
            k_assert(Not a.has_left_child() OrElse Not a.right_child().has_left_child())
            Dim b As node = Nothing
            b = a.right_child()
            a.replace_parent_subtree(b)
            If a.has_left_child() Then
                b.replace_left(a.left_child())
            End If

            b.debug_assert_structure()

            Return b
        End Function

        Private Shared Function replace_by_left_max(ByVal a As node,
                                                    ByRef parent_of_replaced_node As node) As node
            k_assert(Not a Is Nothing)
            k_assert(a.has_left_child())
            Dim b As node = Nothing
            If a.left_child().has_right_child() Then
                b = a.left_child().max()
                k_assert(Not b Is Nothing)
                k_assert(Not b.has_right_child())
                k_assert(object_compare(b, a.left_child()) <> 0)
                k_assert(b.has_parent())
                k_assert(b.is_right_subtree())
                parent_of_replaced_node = b.parent()
                If b.has_left_child() Then
                    b.replace_by_left_subtree()
                Else
                    b.parent().clear_right()
                End If
                b = a.replace_by(b)
            Else
                parent_of_replaced_node = a.parent()
                b = a.replace_by_left_subtree()
            End If
            b.debug_assert_structure()
            If Not parent_of_replaced_node Is Nothing Then
                parent_of_replaced_node.debug_assert_structure()
            End If

            Return b
        End Function

        Private Shared Function replace_by_right_min(ByVal a As node,
                                                     ByRef parent_of_replaced_node As node) As node
            k_assert(Not a Is Nothing)
            k_assert(a.has_right_child())
            Dim b As node = Nothing
            If a.right_child().has_left_child() Then
                b = a.right_child().min()
                k_assert(Not b Is Nothing)
                k_assert(Not b.has_left_child())
                k_assert(object_compare(b, a.right_child()) <> 0)
                k_assert(b.has_parent())
                k_assert(b.is_left_subtree())
                parent_of_replaced_node = b.parent()
                If b.has_right_child() Then
                    b.replace_by_right_subtree()
                Else
                    b.parent().clear_left()
                End If
                b = a.replace_by(b)
            Else
                parent_of_replaced_node = a.parent()
                b = a.replace_by_right_subtree()
            End If

            b.debug_assert_structure()
            If Not parent_of_replaced_node Is Nothing Then
                parent_of_replaced_node.debug_assert_structure()
            End If

            Return b
        End Function

        Private Shared Function [erase](ByVal n As node,
                                        ByVal select_left As Boolean,
                                        ByRef parent_of_removed_node As node) As node
            k_assert(Not n Is Nothing)
            Dim r As node = Nothing
            If n.has_left_child() AndAlso n.has_right_child() Then
                If select_left Then
                    r = n.replace_by_left_max(parent_of_removed_node)
                Else
                    r = n.replace_by_right_min(parent_of_removed_node)
                End If
            Else
                If n.has_left_child() Then
                    r = n.left_child()
                ElseIf n.has_right_child() Then
                    r = n.right_child()
                Else
                    r = Nothing
                End If
                If n.has_parent() Then
                    parent_of_removed_node = n.parent()
                    n.replace_parent_subtree(r)
                Else
                    parent_of_removed_node = Nothing
                End If
            End If

            If Not r Is Nothing Then
                r.debug_assert_structure()
            End If
            If Not parent_of_removed_node Is Nothing Then
                parent_of_removed_node.debug_assert_structure()
            End If

            Return r
        End Function

        Public Function revise_parent_subtree_height() As Boolean
            k_assert(has_parent())
            If is_left_subtree() Then
                Return parent().revise_left_subtree_height()
            Else
                k_assert(is_right_subtree())
                Return parent().revise_right_subtree_height()
            End If
        End Function

        Public Function revise_or_clear_left_subtree_height() As Boolean
            Dim n As UInt32 = 0
            n = If(has_left_child(), left_child().boxed_subtree_height(), 0)
            If boxed_left_subtree_height() <> n Then
                heighted_box().left_height = n
                Return True
            Else
                Return False
            End If
        End Function

        Public Function revise_or_clear_right_subtree_height() As Boolean
            Dim n As UInt32 = 0
            n = If(has_right_child(), right_child().boxed_subtree_height(), 0)
            If boxed_right_subtree_height() <> n Then
                heighted_box().right_height = n
                Return True
            Else
                Return False
            End If
        End Function

        Public Function revise_left_subtree_height() As Boolean
            k_assert(has_left_child())
            Return revise_or_clear_left_subtree_height()
        End Function

        Public Function clear_left_subtree_height() As Boolean
            k_assert(Not has_left_child())
            Return revise_or_clear_left_subtree_height()
        End Function

        Public Function revise_right_subtree_height() As Boolean
            k_assert(has_right_child())
            Return revise_or_clear_right_subtree_height()
        End Function

        Public Function clear_right_subtree_height() As Boolean
            k_assert(Not has_right_child())
            Return revise_or_clear_right_subtree_height()
        End Function
    End Class
End Class
